;; nreinas.lisp - Solución al problema de las N reinas
;;
;;  Autores:
;;    Federico Churca Torrusio <fchurca@fi.uba.ar>
;;      FIUBA - Universidad de Buenos Aires, Facultad de Ingeniería
;;      Buenos Aires, Argentina
;;    Federico Farina <federicofarina22@gmail.com>
;;      FIUBA - Universidad de Buenos Aires, Facultad de Ingeniería
;;      Buenos Aires, Argentina

;;;; Solución funcional

;;;
(defun captures-p (row1 row2 columns)
"
;;; Predicado para verificar si dos reinas se capturan entre sí
;;;
;;; row1:    Fila donde esta la reina 1
;;; row2:    Fila donde esta la reina 2
;;; columns: Cantidad de columnas que separan a las reinas
;;;
;;; Devuelve T si las reinas se capturan entre sí y NIL si no lo hacen
"
  (let ((rows (- row1 row2)))
    (or
      (eql rows 0)                ; Están en la misma fila
      (eql columns 0)             ; Están en la misma columna
      (eql columns (abs rows))))) ; Están en diagonal

;;;
(defun valid-board-p (board)
"
;;; Predicado para verificar si un tablero es válido
;;;
;;; board: El tablero a verificar
;;;
;;; Devuelve T si el tablero es válido y NIL si no lo es
"
  (unless (null board)            ; Un tablero vacío siempre es inválido
    (destructuring-bind (current-row &rest remaining) board
      (and
        ;; La reina en la primera columna no captura ninguna otra
        (loop for other-row in remaining for columns from 1
          never (captures-p current-row other-row columns))
        ;; No hay más tablero o el subtablero remanente es válido
        (or (null remaining) (valid-board-p remaining))))))

;;;
(defun generate-valid-boards (size &optional (postfix ()))
"
;;; Genera tableros de n reinas válidos de cierto tamaño
;;;
;;; size:    Tamaño de los tableros a generar
;;; postfix: Subtablero a usar como posfijo de los tableros generados
;;;          Por defecto es la lista vacía
;;;
;;; Devuelve una lista de los tableros de n reinas válidos del tamaño dado que
;;; tengan sus últimas columnas según el posfijo
"
  ;; Si el tablero posfijo es un tablero inválido no vacío, no se genera
  ;; ningún resultado (se devuelve NIL que es también la lista vacía)
  (when (or (valid-board-p postfix) (null postfix))
    (if (> size (length postfix))
      (loop for i from 1 to size
        append (generate-valid-boards size (cons i postfix)))
      (unless (null postfix) (list postfix)))))

;;;; Funciones para mostrar los resultados

;;;
(defun print-board (board)
"
;;; Imprime en pantalla un tablero de N-reinas
;;;
;;; board: El tablero a imprimir
;;;
;;; Devuelve el tablero pasado por parámetro
"
  (format t "~2&Tablero: ~a" board)
  (dolist (row board)
    (format t "~&")
    (loop for i from 1 to (length board) do
      (format t "~c|" (if (eql i row) #\# #\_))))
  board)

;;;
(defun print-valid-boards (size)
"
;;; Genera e imprime en pantalla los tableros de n reinas de cierto tamaño
;;;
;;; size: Tamaño de los tableros a generar e imprimir
;;;
;;; Devuelve una lista de los tableros de n reinas válidos del tamaño dado
"
  (let ((boards (generate-valid-boards size)))
    (dolist (board boards) (print-board board))
    (format t "~3&~d Tablero~:*~p válido~:*~p de tamaño ~d"
      (length boards) size)
    boards))

